import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2022-09-16
 * Time:22:24
 */

/**
 * 力扣897:递增顺序搜索数
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class increasingBST {
    public  TreeNode increasingBST(TreeNode root) {
        //建立列表
        List<Integer> list = new ArrayList<>();
        //中序遍历
        inorder(root,list);

        TreeNode newHead = new TreeNode(-1);
        TreeNode curnewHead = newHead;
        for(int num: list){
            curnewHead.right = new TreeNode(num);
            curnewHead = curnewHead.right;
        }
        return newHead.right;
    }
    public void inorder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
}
